package leetcode;

import java.util.*;

public class Lc373 {


    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {

        int m = nums1.length;
        int n = nums2.length;
        List<List<Integer>> ans = new ArrayList<>();
        if (m == 0 || n == 0) {
            return ans;
        }
        PriorityQueue<Pair> pq = new PriorityQueue<>(new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                return (nums1[o1.i] + nums2[o1.j]) - (nums1[o2.i] + nums2[o2.j]);
            }
        });
//        boolean[][] visited = new boolean[m][n]; // boolean数组会超内存
//        visited[0][0] = true;
        HashSet<Pair> visited = new HashSet<>();
        Pair pair = new Pair(0, 0);
        pq.offer(pair);
        visited.add(pair);
        while (!pq.isEmpty() && k > 0) {
            int i = pq.peek().i;
            int j = pq.poll().j;
            ans.add(Arrays.asList(nums1[i], nums2[j]));
            Pair temp = new Pair(i + 1, j);
            if ((i + 1) < m && !visited.contains(temp)) {
                pq.offer(new Pair(i + 1, j));
                visited.add(temp);
            }
            temp = new Pair(i, j + 1);
            if ((j + 1) < n && !visited.contains(temp)) {
                pq.offer(new Pair(i, j + 1));
                visited.add(temp);
            }
            k--;
        }
        return ans;
    }

//    public static void main(String[] args) {
//        Lc373 lc373 = new Lc373();
//        int[] a1 = {-10,-4,0,0,6};
//        int[] a2 = {3,5,6,7,8,100};
//        int k = 10;
//        System.out.println(lc373.kSmallestPairs(a1, a2, k));
//    }

}
class Pair {
    public int i, j;
    public Pair(int i, int j) {
        this.i = i;
        this.j = j;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Pair pair = (Pair) o;
        return i == pair.i && j == pair.j;
    }

    @Override
    public int hashCode() {
        return Objects.hash(i, j);
    }
}